import java.util.ArrayList;
import java.util.List;

/**
 * 1780. 判断一个数字是否可以表示成三的幂的和
 * https://leetcode-cn.com/problems/check-if-number-is-a-sum-of-powers-of-three/
 */
public class Solutions_1780 {
    public static void main(String[] args) {
        int n1 = 12;  // output: true    9 + 3
        int n2 = 91;  // output: true    81 + 9 + 1
        int n3 = 21;  // output: false

        List<Integer> inputs = new ArrayList<>();
        inputs.add(n1);
        inputs.add(n2);
        inputs.add(n3);

        for (int input : inputs) {
            boolean result = checkPowersOfThree(input);
            System.out.println(result);
        }
    }

    /**
     * 解法二：数学法（三进制）
     * 判断 n 能否转换成合法的 3 进制
     * 91 = (10101)3  = 3^4 + 3^2 + 3^0 = 81 + 9 + 1
     * 12 = (110)3    = 3^2 + 3^1 = 9 + 3
     * 21 = (210)3    无法转换成三进制：进制中只能包含 0 和 1
     */
    public static boolean checkPowersOfThree(int n) {
        while (n > 0) {
            if (n % 3 == 2) {
                // bit 位上，只能是 0 和 1
                return false;
            }
            n /= 3;
        }
        return true;
    }

    /**
     * 解法一：数学法（类似贪心）
     */
    public static boolean checkPowersOfThree2(int n) {
        // n 最大不会大于 3^15
        for (int i = 15; i >= 0; i--) {
            int cur = (int) Math.pow(3, i);
            if (n >= cur) {
                // 若 n 大于等于 cur，则依次减去 cur
                n -= cur;
            }
        }
        // 最终 n 为 0，说明可以由不同的 3 的幂的数组成
        return n == 0;
    }
}
